package offer;

import java.util.ArrayList;
import java.util.List;

public class ex_1 {
    public static void main(String[] args) {
        List<Integer> copyList = findCopy(new int[]{2, 3, 1, 0, 2, 5, 3});
        System.out.println(copyList);
    }

    /**
     * 找出数组中重复的数字
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
     * 请找出数组中任意一个重复的数字。
     * 输入：
     * [2, 3, 1, 0, 2, 5, 3]
     * 输出：2 或 3
     * 2 <= n <= 100000
     */
    static List<Integer> findCopy(int numbers[]) {
        int len = numbers.length;
        if (len==0){
            return new ArrayList<>();
        }
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            while (numbers[i]!=i) {
                int temp = numbers[i];
                if (numbers[temp]==temp) {
                    duplicates.add(numbers[temp]);
                    break;
                } else  {
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
        }
        return duplicates;
    }


}
